A mapping of $k$-bit strings into $n$-bit strings is called an$(\alpha,\beta)$-map if $k$-bit strings which are more than $\alpha k$ apartare mapped to $n$-bit strings that are more than $\beta n$ apart. This is arelaxation of the classical problem of constructing error-correcting codes,which corresponds to $\alpha=0$. Existence of an $(\alpha,\beta)$-map isequivalent to existence of a graph homomorphism $\bar H(k,\alpha k)\to \barH(n,\beta n)$, where $H(n,d)$ is a Hamming graph with vertex set $\{0,1\}^n$and edges connecting vertices differing in $d$ or fewer entries. This paper proves impossibility results on achievable parameters$(\alpha,\beta)$ in the regime of $n,k\to\infty$ with a fixed ratio ${n\overk}= \rho$. This is done by developing a general criterion for existence ofgraph-homomorphism based on the semi-definite relaxation of the independencenumber of a graph (known as the Schrijver's $\theta$-function). The criterionis then evaluated using some known and some new results from coding theoryconcerning the $\theta$-function of Hamming graphs. As an example, it is shownthat if $\beta>1/2$ and $n\over k$ -- integer, the ${n\over k}$-fold repetitionmap achieving $\alpha=\beta$ is asymptotically optimal. Finally, constraints on configurations of points and hyperplanes inprojective spaces over $\mathbb{F}_2$ are derived.
展开▼
机译：如果将距离$ \ alpha k $的$ k $位字符串映射到$，则将$ k $位的字符串映射到$ n $位的字符串称为$（\ alpha，\ beta）$-map。大于$ \ beta n $的n $位字符串。这是构造纠错码的经典问题的放松，它对应于$ \ alpha = 0 $。 $（\ alpha，\ beta）$映射的存在与图同态$ \ bar H（k，\ alpha k）\至\ barH（n，\ beta n）$的存在等效，其中$ H（n ，d）$是汉明图，其顶点集为$ \ {0,1 \} ^ n $，并且其边连接的顶点不同，但点数为$ d $或更少。本文证明了在固定比率$ {n \ overk} = \ rho $的情况下，在$ n，k \ to \ infty $体制中可实现参数$（\ alpha，\ beta）$的不可能结果。这是通过基于图的独立数的半确定松弛（称为Schrijver的$ \ theta $函数）开发图同态存在的一般准则来完成的。然后使用有关汉明图的\ theta $函数的编码理论的一些已知结果和一些新结果对标准进行评估。作为示例，表明如果$ \ beta> 1/2 $和$ n \ over k $-整数，达到$ \ alpha = \ beta $的$ {n \ over k} $倍重复映射是渐近最优的。最后，推导了对投影空间\\ mathbb {F} _2 $上的点和超平面的配置的约束。
展开▼
